class Solution {
    public:
        int numSquares(int n) {
            int m = sqrt(n);
            vector<vector<int>> dp(m+1,vector<int>(n+1));
            dp[0][0] = 0; //包装后面填表正确
            for(int i = 1 ; i < n+1 ;i++)   dp[0][i] = 0x3f3f3f3f;
            for(int i = 1 ; i < m+1 ;i++){
                for(int j = 0 ; j <n+1; j++ ){
                    dp[i][j] = j>=i*i ? min(dp[i-1][j],dp[i][j-i*i]+1) : dp[i-1][j] ;
                }
            }
            return dp[m][n];
        }
    };